//package work.rightAnswer;
//
//import java.util.ArrayList;
//import java.util.Arrays;
//import java.util.List;
//
//class N_queen_51 {
//    List<List<String>> result = new ArrayList<>();
//    public List<List<String>> solveNQueens(int n) {
//        char[][] chess = new char[n][n];
//        for (char[] chars : chess) {
//            Arrays.fill(chars,'.');
//        }
//        backtracing(chess,0,n);
//        return result;
//    }
//
//    private void backtracing(char[][] chess, int startIndex, int n) {
//        if(startIndex>=n){
//            List<String> path = new ArrayList<>();
//            for (char[] chars : chess) {
//                String str = new String(chars);
//                path.add(str);
//            }
//            result.add(new ArrayList<>(path));
//            return;
//        }
//
//        char[] arr = chess[startIndex];
//        for (int i = 0; i < arr.length; i++) {
//            chess[startIndex][i]='Q';
//            if(isVaild(chess,startIndex,i)){
//                backtracing(chess,startIndex+1,n);
//            }
//            chess[startIndex][i]='.';
//        }
//
//    }
//
//    private boolean isVaild(char[][] chess, int x, int y) {
//        //竖直方向上
//        for (int i = 0; i < x; i++) {
//            if(chess[i][y] == 'Q'){
//                return false;
//            }
//        }
//
//        //45°方向上
//        int i = x-1;
//        int j = y+1;
//        while (i>=0&&j<chess[0].length){
//            if(chess[i][j]=='Q'){
//                return false;
//            }
//            i--;
//            j++;
//        }
//
//        //135°方向上
//        i = x-1;
//        j = y-1;
//        while (i>=0&&j>=0){
//            if(chess[i][j]=='Q'){
//                return false;
//            }
//            i--;
//            j--;
//        }
//
//        return true;
//    }
//}